package com.cskaoyan.com.ex;

public class Ex1 {
    public static void main(String[] args) {


//        求链表的中间元素
//        判断链表中是否有环(circle)
//        反转单链表
        Node e = new Node("e", null);
        Node d = new Node("d", e);
        Node c = new Node("c", d);
        Node b = new Node("b", c);
        Node a = new Node("a", b);

        // a --> b --> c  --> d --> e
//        求链表的中间元素

        // a --> b --> c  --> d
        d.next = null;

        String value = getMid(a);
        System.out.println(value);
    }

    /**
     * 给定链表的头结点, 获取这个链表的中间位置的结点存储的内容
     * (如果是偶数个, 偏中间几个)
     * @param head: 给定链表的头结点
     * @return: 中间结点存储的内容
     */
    private static String getMid(Node head) {
        // 快慢指针
        // a --> b --> c  --> d --> e
        //            |
        //                         |

        Node l = head; // 满指针
        Node f = head; // 快指针

        // a --> b --> c  --> d
        //            |
        //                          |

        // 快指针后面还有数据/结点(!= null)  --> 可以接着向后走
        while (f.next != null  && f.next.next != null ){
            l = l.next; // 慢指针一次走一步
            f = f.next.next; // 快指针一次走两步
        }

        // 快指针走到尾部, 慢指针走到中间
        return l.value;
    }
}
// 单链表的结点
class Node{
    String value;
    Node next;
    public Node(String value, Node next) {
        this.value = value;
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value='" + value + '\'' +
                ", next=" + next +
                '}';
    }
}
